//N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
//要求：任何两个皇后不同行，不同列也不在同一条斜线上，
//求给一个整数 n ，返回 n 皇后的摆法数。

//思路:逐行进行，每行逐个挑选，当前该格为零则可放置皇后，放置后，将对于这个皇后来说无法放置的位置加1（称为这个皇后带来的影响），接着再次调用函数对下一行进行逐个挑选。
//当最后一行也成功放置之后count++，并返回
//当开始return时（当前放法行不通或当前放法已成功），会依次清除这次放法与其他放法相异的皇后所带来的影响，然后开始尝试其他放法

#include <stdio.h>
#include <stdlib.h>

void setqueen(int n, char** board, int* count, int row)
{
    if(n == row)
    {
        (*count)++;
        return;
    }
    for(int i = 0; i < n; i++)
    {
        if(board[row][i] != 0)
        continue;
        for(int j = row + 1; j < n; j++)//同列为一
        {
            board[j][i] += 1;//加等的目的是在清除当前这行放置产生的影响时，保留上面行数的影响
        }
        for(int j = 1; j < n; j++)//斜线为一
        {
            if((row + j) < n&&(i + j) < n)
            {
                board[row + j][i + j] += 1;
            }
            if((row + j) < n&&(i - j) < n)
            {
                board[row + j][i - j] += 1;
            }
        }
       
        setqueen(n, board, count, row + 1);

        for(int j = row + 1; j < n; j++)
        {
            board[j][i] -= 1;
        }
        for(int j = 1; j < n; j++)
        {
            if((row + j) < n&&(i + j) < n)
            {
                board[row + j][i + j] -= 1;
            }
            if((row + j) < n&&(i - j) < n)
            {
                board[row + j][i - j] -= 1;
            }
        }
    }
    return;
}

int Nqueen(int n ) {
    // write code here
    if(n == 1)
    return 1;
    char** board = (char**)malloc(sizeof(char*) * n);
    for(int i = 0; i < n; i++)
    {
        board[i] = (char*)malloc(sizeof(char) * n);
        for(int j = 0; j < n; j++)
        board[i][j] = 0;
    }

    int count = 0;
    setqueen(n, board, &count, 0);
    return count;

}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int num = Nqueen(n);
    printf("%d", num);
    return 0;
}